//2980. 检查按位或是否存在尾随零

//给你一个 正整数 数组 nums 。
//你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中 至少 存在一个尾随零。
//例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。
//如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。

//class Solution {
//public:
//    bool hasTrailingZeros(vector<int>& nums) {//2的倍数超过两个
//        int even = nums.size();
//        for (int x : nums) {
//            even -= x % 2;
//        }
//        return even >= 2;
//    }
//};

//1318. 或运算的最小翻转次数

//给你三个正整数 a、b 和 c。
//你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算   a OR b == c  成立的最小翻转次数。
//「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

//// class Solution {
//// public:
////     int minFlips(int a, int b, int c) {
////         int ans = 0;
////         for (int i = 0; i < 31; ++i) {
////             int bit_a = (a >> i) & 1;
////             int bit_b = (b >> i) & 1;
////             int bit_c = (c >> i) & 1;
////             if (bit_c == 0) {
////                 ans += bit_a + bit_b;
////             }
////             else {
////                 ans += (bit_a + bit_b == 0);
////             }
////         }
////         return ans;
////     }
//// };
////翻转次数 = (c = 0 and a | b == 1 的位数) + (c = 0 and a == 1 and b == 1 的位数)
//class Solution {
//public:
//    int minFlips(int a, int b, int c) {
//        return popcount(static_cast<uint32_t>((a | b) ^ c)) + popcount(static_cast<uint32_t>(a & b & (~c)));
//    }
//};

//2419. 按位与最大的最长子数组

//给你一个长度为 n 的整数数组 nums 。
//考虑 nums 中进行 按位与（bitwise AND）运算得到的值 最大 的 非空 子数组。
//换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。
//返回满足要求的 最长 子数组的长度。
//数组的按位与就是对数组中的所有数字进行按位与运算。
//子数组 是数组中的一个连续元素序列。

//class Solution {
//public:
//    int longestSubarray(vector<int>& nums) {
//        int ans = 0, mx = 0, cnt = 0;
//        for (int x : nums) {
//            if (x > mx) {
//                mx = x;
//                ans = cnt = 1;
//            }
//            else if (x == mx) {
//                cnt++;
//                ans = max(ans, cnt);
//            }
//            else {
//                cnt = 0;
//            }
//        }
//        return ans;
//    }
//};

//2871. 将数组分割成最多数目的子数组

//给你一个只包含 非负 整数的数组 nums 。
//我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。
//请你将数组分割成一个或者更多子数组，满足：
//每个 元素都 只 属于一个子数组。
//子数组分数之和尽可能 小 。
//请你在满足以上要求的条件下，返回 最多 可以得到多少个子数组。
//一个 子数组 是一个数组中一段连续的元素。

//class Solution {
//public:
//    int maxSubarrays(vector<int>& nums) {
//        int ans = 0;
//        int a = -1;
//        for (int x : nums) {
//            a &= x;
//            if (a == 0) {
//                ans++;
//                a = -1;
//            }
//        }
//        return max(ans, 1);
//    }
//};

//2401. 最长优雅子数组

//给你一个由 正 整数组成的数组 nums 。
//如果 nums 的子数组中位于 不同 位置的每对元素按位 与（AND）运算的结果等于 0 ，则称该子数组为 优雅 子数组。
//返回 最长 的优雅子数组的长度。
//子数组 是数组中的一个 连续 部分。
//注意：长度为 1 的子数组始终视作优雅子数组。

//class Solution {
//public:
//    int longestNiceSubarray(vector<int>& nums) {
//        int ans = 0, left = 0, or_ = 0;
//        for (int right = 0; right < nums.size(); right++) {
//            while (or_ & nums[right]) { // 有交集
//                or_ ^= nums[left++]; // 从 or 中去掉集合 nums[left]
//            }
//            or_ |= nums[right]; // 把集合 nums[right] 并入 or 中
//            ans = max(ans, right - left + 1);
//        }
//        return ans;
//    }
//};

//2680. 最大或值

//给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。
//你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。
//a | b 表示两个整数 a 和 b 的 按位或 运算。

//class Solution {
//public:
//    long long maximumOr(vector<int>& nums, int k) {
//        int n = nums.size();
//        // suf[i] 表示 nums[i+1] 到 nums[n-1] 的 OR
//        vector<int> suf(n);
//        for (int i = n - 2; i >= 0; i--) {
//            suf[i] = suf[i + 1] | nums[i + 1];
//        }
//
//        long long ans = 0;
//        // pre 表示 nums[0] 到 nums[i-1] 的 OR
//        int pre = 0;
//        for (int i = 0; i < n; i++) {
//            ans = max(ans, pre | ((long long)nums[i] << k) | suf[i]);
//            pre |= nums[i];
//        }
//        return ans;
//    }
//};

//3133. 数组最后一个元素的最小值

//给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，
//满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
//返回 nums[n - 1] 可能的 最小 值。

//class Solution {
//public:
//    long long minEnd(int n, int x) {
//        n--;
//        long long ans = x;
//        int i = 0, j = 0;
//        while (n >> j) {
//            // x 的第 i 个比特值是 0，即「空位」
//            if ((ans >> i & 1) == 0) {
//                // 空位填入 n 的第 j 个比特值
//                ans |= (long long)(n >> j & 1) << i;
//                j++;
//            }
//            i++;
//        }
//        return ans;
//    }
//};

//3117. 划分数组得到最小的值之和

//给你两个数组 nums 和 andValues，长度分别为 n 和 m。
//数组的 值 等于该数组的 最后一个 元素。
//你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组[li, ri]，子数组元素的按位 AND 运算结果等于 andValues[i]，换句话说，
//对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，其中 & 表示按位 AND 运算符。
//返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 - 1 。

//class Solution {
//    vector<int> fa;    // 并查集父节点数组
//    vector<int> and_;  // 存储每个连通分量的AND值
//
//    // 并查集查找函数（带路径压缩）
//    int find(int x) {
//        return fa[x] == x ? x : fa[x] = find(fa[x]);
//    };
//
//public:
//    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
//        // 初始化并查集
//        fa.resize(n);
//        ranges::iota(fa, 0); 
//        and_.resize(n, -1);   
//
//        // 处理所有边，构建连通分量并计算每个连通分量的AND值
//        for (auto& e : edges) {
//            int u = e[0], v = e[1], weight = e[2];
//            int x = find(u);  // 找到u所在连通分量的根
//            int y = find(v);  // 找到v所在连通分量的根
//
//            // 将边的权值AND到目标连通分量的AND值中
//            and_[y] &= weight;
//
//            // 如果两个节点不在同一个连通分量中，进行合并
//            if (x != y) {
//                // 将x连通分量的AND值合并到y中
//                and_[y] &= and_[x];
//                // 将x的父节点指向y，完成合并
//                fa[x] = y;
//            }
//        }
//
//        vector<int> ans;
//        ans.reserve(query.size()); 
//
//        // 处理每个查询
//        for (auto& q : query) {
//            int s = q[0], t = q[1
//            ans.push_back(find(s) != find(t) ? -1 : and_[find(s)]);
//        }
//        return ans;
//    }
//};

//3117. 划分数组得到最小的值之和

//给你两个数组 nums 和 andValues，长度分别为 n 和 m。
//数组的 值 等于该数组的 最后一个 元素。
//你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组[li, ri]，子数组元素的按位 AND 运算结果等于 andValues[i]，换句话说，
//对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，其中 & 表示按位 AND 运算符。
//返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 - 1 。

//class Solution {
//public:
//    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
//        const int INF = 0x3f3f3f3f;
//        int n = nums.size();
//        vector<int> f(n + 1, INF);
//        vector<int> new_f(n + 1);
//
//        f[0] = 0;
//        for (int target : andValues) {
//            auto a = nums;
//            int left = 0, right = 0;
//            deque<int> q; // 单调队列，保存 f 的下标
//            int qi = 0; // 单调队列目前处理到 f[qi]
//
//            new_f[0] = INF;
//            for (int i = 0; i < n; i++) {
//                int x = a[i];
//                for (int j = i - 1; j >= 0 && (a[j] & x) != a[j]; j--) {
//                    a[j] &= x;
//                }
//                while (left <= i && a[left] < target) {
//                    left++;
//                }
//                while (right <= i && a[right] <= target) {
//                    right++;
//                }
//
//                // 上面这段的目的是求出子数组右端点为 i 时，子数组左端点的最小值和最大值+1
//                // 下面是单调队列的滑窗过程
//
//                if (left < right) {
//                    // 单调队列：右边入
//                    for (; qi < right; qi++) {
//                        while (!q.empty() && f[qi] <= f[q.back()]) {
//                            q.pop_back();
//                        }
//                        q.push_back(qi);
//                    }
//
//                    // 单调队列：左边出
//                    while (q.front() < left) {
//                        q.pop_front();
//                    }
//
//                    // 单调队列：计算答案
//                    new_f[i + 1] = f[q.front()] + x; // 队首就是最小值
//                }
//                else {
//                    new_f[i + 1] = INF;
//                }
//            }
//            swap(f, new_f);
//        }
//        return f[n] < INF ? f[n] : -1;
//    }
//};